/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/insert-delete-getrandom-o1
   @Language: C++
   @Datetime: 19-06-12 16:29
   */

class RandomizedSet {
	unordered_map<int,int> dict;
	vector<int> data;
public:
	RandomizedSet() {
		// do intialization if necessary
	}

	/*
	 * @param val: a value to the set
	 * @return: true if the set did not already contain the specified element or false
	 */
	bool insert(int val) {
		// write your code here
		if(dict.count(val)) return false;
		data.push_back(val);
		dict[val]=data.size()-1;
		return true;
	}

	/*
	 * @param val: a value from the set
	 * @return: true if the set contained the specified element or false
	 */
	bool remove(int val) {
		// write your code here
		if(dict.count(val)==0) return false;
		dict[data.back()]=dict[val];
		swap(data[dict[val]],data[data.size()-1]);
		dict.erase(val);
		data.pop_back();
		return true;
	}

	/*
	 * @return: Get a random element from the set
	 */
	int getRandom() {
		// write your code here
		return data[rand()%data.size()];
	}
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param = obj.insert(val);
 * bool param = obj.remove(val);
 * int param = obj.getRandom();
 */
